In packet-switched networks, routers, switches, and gateways are examples of the types of network devices that effect delivery of packets from source endpoints to destination endpoints. These routing devices receive network packets at one or more ingress ports. For each received packet, the routing device examines one or more of the packet's headers and then determines an egress port that will move the packet most effectively towards its destination. The device switches the packet to that egress port, where it will be placed back on the network to wend its way towards the destination endpoint.
Routing devices generally queue a packet in an internal queue until the packet can be switched to the appropriate egress port, and/or until the egress port has transmitted earlier-arriving packets. These queues must generally be large enough to accommodate traffic bursts—such a burst can occur, e.g., when packets arriving at roughly the same time at multiple ingress ports must be switched to the same egress port. But if the queues are allowed to grow too large, arriving packets are unduly delayed in the router, resulting in service degradation for many forms of traffic. This condition is generally referred to as router “congestion”.
Sophisticated routing devices employ active queue management strategies to keep queue sizes within a desired operating range, thereby avoiding congestion. For example, because most of the traffic on a packet-switched network is not allotted a dedicated circuit, transmitting devices are usually expected to conform to a traffic profile that specifies an average and a peak data rate for that device. When a transmitting device fails to conform to its profile, a router may choose to “drop”, or discard, some of the packets from the device in order to place the data rate back within profile. By dropping packets from the offending endpoint, the router prevents that endpoint from consuming an unfair portion of a router queue. Also, TCP and TCP-like applications interpret packet loss as an indicator of congestion, scale back their rate, and then ramp back up in a “slow-start” mode.
Unfortunately, transient congestion can occur at a router even when all endpoints are behaving in a reasonable manner. Under these conditions, the router must generally choose some packets to be discarded, hopefully in a manner that is both “fair” and causes traffic to return to a reasonable level. Early routers often implemented Drop Tail or Random Drop algorithms. Drop Tail simply drops a packet which arrives to a full queue. Random Drop drops one packet at random from the queue when a packet arrives to a full queue.
Researchers found that several undesirable situations can arise with the Drop Tail and Random Drop algorithms. Because these algorithms were reactive rather than proactive, no control was exercised until congestion was actually occurring. This results in a phenomenon termed “global synchronization”, which causes a large number of senders to reduce their rates in lockstep as a result of congestion, resulting in periods of high drop rates followed by periods of network underutilization. It was also found that misbehaving users were not always effectively controlled by these schemes.
Floyd and Jacobson proposed a different congestion avoidance algorithm to deal with these problems. “Random Early Detection Gateways for Congestion Avoidance”, IEEE/ACM Trans. On Networking, August 1993. The desired congestion response of the Random Early Detection (RED) algorithm proposed by Floyd and Jacobson is depicted in FIG. 1. An average queue size avg, i.e., a low-pass filtered version of the instantaneous queue size, is calculated. When avg is below a lower threshold minth, no packets are dropped. When avg is above an upper threshold maxth (which is preferably less than the queue's maximum capacity), all packets are dropped. When avg is between these two extremes, an initial packet-marking probability pb varies linearly between 0 and Pmark:pb←Pmark(avg−minth)/(maxth−minth).
The final packet-marking probability pa increases slowly as the count increases since the last marked packet:pa←pb/(1−count·pb).
Basing the final packet-marking probability on count ensures that the algorithm will not wait too long before marking a packet.
When a packet arrives at a RED-enabled queue, the average queue size is used to determine an operating point on the curve of FIG. 1. The operating point, together with count, defines a packet discard probability pa. A random trial determines whether the current packet will be discarded or not, with the “discard” outcome having a probability equal to the packet discard probability pa.
The RED algorithm has several desirable characteristics. Because it uses a filtered queue size, it does not react strongly to short-duration traffic bursts. The probability that a given endpoint's traffic will be dropped is roughly proportional to that endpoint's share of the overall traffic load in the queue. Traffic is managed before congestion reaches a critical level. And dropped packets are spread somewhat randomly within the traffic pattern, instead of being bunched together.
FIG. 2 shows one variation on the RED congestion avoidance approach. Traffic that is “out-of-profile”, i.e., not conforming to its allowable rates, is controlled using a first RED threshold set Ominth and Omaxth. Traffic that is “in-profile” is controlled using a second RED threshold set Iminth and Imaxth. In operation, out-of-profile traffic will be dropped under the FIG. 2 scheme at a higher rate than in-profile traffic for most average queue sizes.